#ifndef TREE_TYPE_HPP
#define TREE_TYPE_HPP

#include <cstdint>
#include <unordered_map>
#include <utility>
#include <vector>
#include "ccr/graph_type.hpp"

#define MERGE_TO_UINT64(high, low) \
  ((static_cast<uint64_t>(high) << 32) | static_cast<uint64_t>(low))

struct Node {
  int id = -1;
  int in_tree = false;
};

using black_table = std::pair<int32_t, int32_t>;

using section_table = std::pair<int32_t, int32_t>;

using NodeList = std::vector<Node>;

struct Tree {
  GRA graph_;
  NodeList vl_;
  int vsize_;
  int root_ = -1;
  int m = 1;  // 用于确定区间
  bool isinverse = false;
  // 每个黑色节点最近的红色祖先节点、红色子孙节点
  std::vector<black_table> black_table_;

  // TODO：label标签，每个红色节点维护一个区间
  std::vector<section_table> section_table_;

  // true:红色，false:黑色
  std::vector<bool> color_;

  // 0 黑色节点， 1 CrossEdge的起点， 2 CrossEdge的终点, 3 既是终点又是起点
  std::vector<int> isStart_;

  Tree(int n) {
    graph_ = GRA(n, In_OutList());
    vl_ = NodeList(n);
    // color_ = std::vector<bool>(n, false);
    isStart_ = std::vector<int>(n, 0);
    black_table_ = std::vector<black_table>(n, std::make_pair(-1, -1));
    section_table_ = std::vector<section_table>(n, std::make_pair(-1, -1));
  }
  Tree() = default;

  inline void set_num(int n) {
    graph_ = GRA(n, In_OutList());
    vl_ = NodeList(n);
  }
  int num_vertices() { return vl_.size(); }
  EdgeList in_edges(int trg) { return graph_[trg].inList; }
  int in_degree(int trg) { return graph_[trg].inList.size(); }
  int out_degree(int trg) { return graph_[trg].outList.size(); }
  inline bool has_node(int num) {
    if (num >= vsize_)
      return false;
    if (graph_[num].inList.empty() && graph_[num].outList.empty())
      return false;
    return true;
  }
};


#endif